package 数据结构专栏.简单级别;

import 数据结构专栏.B_链表专栏.ListNode;

/**
 * @DESC 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * https://leetcode-cn.com/problems/reverse-linked-list/
 * @Author tzq
 * @Date 2020-03-27 20:45
 **/
public class _206_反转链表 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        ListNode l6 = null;
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = l6;
        printList(l1);

//        printList(reverseList(l1));
//        printList(reverseList2(l1));
        printList(reverseList3(l1));

    }

    /**
     * 递归 https://blog.csdn.net/qq_33958946/article/details/84326965
     *
     * <p>
     * 如果当前节点或者当前节点的下一节点为空，直接返回该节点；
     * 否则使该节点的后一节点指向该节点，以此递归。
     *
     * @param head
     * @return
     */
    public static ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode nextNode = head.next; //得到当前节点的下一节点
        head.next = null; //打断当前指针链
        ListNode res = reverseList3(nextNode); //每次递归下一节点进行反转
        nextNode.next = head;//反转指针域
        return res;
    }

    /**
     * 迭代方式实现
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     *
     * @return
     */
    public static ListNode reverseList(ListNode curr) {
        ListNode prev = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /**
     * 递归版本
     *
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }


    /**
     * 打印链表
     *
     * @param node
     */
    public static void printList(ListNode node) {
        if (node == null) return;
        if (node.next != null) {
            System.out.print(node.val + "->");
        } else {
            System.out.println(node.val);
        }
        printList(node.next);
    }
}

